

class ArrayDeQueue:
    """
    Double-ended queue implementation using a python list as underlying storage
    """
    DEFAULT_CAPACITY = 10

    def __init__(self):
        """
        create empty queue
        """
        self._data = [None] * ArrayDeQueue.DEFAULT_CAPACITY
        self._front = 0  # the front of dequeue
        self._size = 0

    def __len__(self):
        return self._size

    def __str__(self):
        return str(self._data[0:self._size])

    def is_empty(self):
        return self._size == 0

    def first(self):
        """
        Return the element at the front of the queue
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty.")
        return self._data[self._front]

    def last(self):
        """
        Rturn the element of the tail of the queue
        :return:
        """
        if self.is_empty():
            raise Exception("queue is empty.")
        tail = (self._front + self._size - 1) % len(self._data)
        return self._data[tail]

    def add_first(self, value):
        """
        Add the value to front of the queue.
        :param value:
        :return:
        """
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        self._front = (self._front - 1) % len(self._data)
        self._data[self._front] = value
        self._size += 1

    def add_last(self, value):
        """
        Add the value to last of the queue.
        :param value:
        :return:
        """
        if self._size == len(self._data):
            self._resize(2 * len(self._data))

        #Insert tail postion
        tail = (self._front + self._size) % len(self._data)
        self._data[tail] = value
        self._size += 1

    def del_first(self):
        """
        Delete the value to front of the queue.
        :return:
        """
        if self.is_empty():
            raise Exception("dequeue is empty")

        if 0 < self._size < len(self._data)//4:
            self._resize(len(self._data)//2)

        value = self._data[self._front]
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return value

    def del_last(self):
        """
        Delete the value to last of the queue.
        :param value:
        :return:
        """
        if self.is_empty():
            raise Exception("dequeue is empty")

        if 0 < self._size < len(self._data)//4:
            self._resize(len(self._data)//2)
        tail = (self._front + self._size - 1) % len(self._data)
        value = self._data[tail]
        self._size -= 1
        return value

    def _resize(self, length):
        # 缓存旧数据
        old = self._data
        self._data = [None] * length

        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0

